package wxy;

import java.util.Arrays;

public class LeetCode105 {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            int n = preorder.length;
            if (n == 0) {
                return null;
            }
            int curVal = preorder[0];
            int idxOfInorder = -1;
            for (int i = 0; i < n; i++) {
                if (inorder[i] == curVal) {
                    idxOfInorder = i;
                    break;
                }
            }
            int leftLength = idxOfInorder - 0;
            int rightLength = n - idxOfInorder - 1;
            TreeNode curNode = new TreeNode();
            curNode.val = curVal;
            curNode.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + leftLength), Arrays.copyOfRange(inorder, 0, leftLength));
            curNode.right = buildTree(Arrays.copyOfRange(preorder, 1 + leftLength, rightLength), Arrays.copyOfRange(inorder, idxOfInorder + 1, rightLength));
            return curNode;
        }
    }
}
